package com.xxwy.lintcode;

/**
 * @author xxwy
 * on 2018/10/10 0010
 * Paint House
 */
public class Num515 {
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
        //一共对少栋房子
        int n = costs.length;
        if (n == 0) {
            return 0;
        }
        int[][] f = new int[n + 1][3];
        //初始化
        f[0][0] = f[0][1] = f[0][2] = 0;
        int i, j, k;
        for (i = 1; i < n + 1; i++) {
            //这一栋房子的颜色
            for (j = 0; j < 3; j++) {
                f[i][j] = Integer.MAX_VALUE;
                //上一栋房子的颜色
                for (k = 0; k < 3; k++) {
                    if (k == j) {
                        continue;
                    }
                    //前一栋放着K颜色的值 + 我这栋房子J颜色的值
                    int value = f[i - 1][k] + costs[i - 1][j];
                    if (value < f[i][j]) {
                        f[i][j] = value;
                    }
                }
            }
        }
        return Math.min(Math.min(f[n][0],f[n][1]),f[n][2]);

    }
}
